package top.minuy.structure.graph.mst;

import top.minuy.algorithm.sort.quick.QuickSort;
import top.minuy.structure.graph.cc.bfs.WeightedCC;
import top.minuy.structure.graph.representations.WeightedEdge;
import top.minuy.structure.graph.representations.table.WeightedGraph;
import top.minuy.structure.tree.unifind.UnionFindV6;

import java.util.ArrayList;
import java.util.List;

/**
 * Kruskal 最小生成树算法
 *
 * @author Minuy
 * @time 15:48
 * @date 2021/11/25
 */
public class Kruskal {

    List<WeightedEdge> mst;

    public Kruskal(WeightedGraph g) {

        mst = new ArrayList<>();

        WeightedCC cc = new WeightedCC(g);
        if (cc.count() != 1) { // 如果不是联通图，直接退出，没有最小生成树
            return;
        }

        // 获取所有的边
        int i = 0;
        WeightedEdge[] edges = new WeightedEdge[g.E()];
        for (int v = 0; v < g.V(); v++) {
            for (int w : g.adj(v)) { // 遍历边
                if (v < w) { // 因为是有两边，所以只取一条
                    edges[i] = new WeightedEdge(v, w, g.getWeight(v, w));
                    i++;
                }
            }
        }

        // 对所有边排序
        QuickSort.sort(edges);

        // 并查集，查看顶点是否在同一联通分量里
        UnionFindV6 uf = new UnionFindV6(g.V());
        // 从排序好的边里从小到大（权值）依次选择
        for (WeightedEdge edge : edges) {
            int v = edge.v;
            int w = edge.w;
            // 判断边的两端是否是联通的，联通的说明组成了环
            if (!uf.isConnected(w, v)) {
                mst.add(edge); // 没联通就是可以选择的
                uf.unionElements(w, v); // 设置为联通
            }
        }
    }

    /**
     * 获取最小生成树
      * @return Iterable<WeightedEdge> 最小生成树的所有边
     * @author Minuy
     * @date 2021/11/25 16:47
     */
    public Iterable<WeightedEdge> mst(){
        return mst;
    }

    @Override
    public String toString() {
        return mst().toString();
    }
}
